package com.zhengwl.study.datastruct;

public class BagQuestion {

	private int[] w;
	private int[] v;
	private int len = 0;

	public BagQuestion(int[] weight, int[] values) {
		this.w = weight;
		this.v = values;
		this.len = weight.length;
	}

	/**
	 * 
	 * @param idx
	 *            从几号元素开始搜索
	 * @param s
	 *            已装物品的重量
	 * @param W   背包的最大容量
	 * @return
	 */
	private int search(int idx, int s, int W) {
		// 已经没有物品搜索了
		if (idx >= len) {
			return 0;
		}
		// 如果装不下这件物品，直接返回不拿这件物品的重量即可
		if (s + w[idx] > W) {
			return search(idx + 1, s, W);
		}
		// 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
		return Math.max(search(idx + 1, s + w[idx], W) + v[idx], search(idx + 1, s, W));
	}

	/**
	 * @param w
	 *            物品重量
	 * @param v
	 *            物品价值
	 * @param W
	 *            背包的最大容量
	 * @return 最大价值
	 */
	public int solve(int W) {
		return search(0, 0, W);
	}
	
	/**
	 * 递推式记忆化搜索(dp)
	 * @param W
	 * @return
	 */
	public int solvedp(int W) {
	    int n = w.length;
	    int[][] dp = new int[n + 1][W + 1];
	    for (int i = 0; i < n; i++) {
	        for (int j = 0; j <= W; j++) {
	            if (j < w[i]) {
	                dp[i + 1][j] = dp[i][j];
	            } else {
	                dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);
	            }
	        }
	    }
	    return dp[n][W];
	}
}
